package com.justnow.offer;

/**
 * 三种情况：
 * 1. 如果p和q分别是root的左右节点，那么root就是我们要找的公共祖先
 * 2. 如果p和q都是root的左节点，以当前节点的左子节点作为参数，进行递归
 * 3. 如果p和q都是root的右节点，以当前节点的左子节点作为参数，进行递归
 */
public class Solution68_2 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
       if (root == null || root == p || root == q)
           //如果root是null，说明已经找到最底了，返回null表示没有找到
           //如果root与p相等或者与q相等，则返回root，root就是我们需要找的祖先节点
           return root;
       //分别进入左子树和右子树，进行递归。
        //如果做子树没有找到，递归函数返回null，证明p和q同时在root的右侧，那么最终的公共祖先就是右子树找到的结点
       TreeNode left = lowestCommonAncestor(root.left, p, q);

        //如果做子树没有找到，递归函数返回null，证明p和q同时在root的右侧，那么最终的公共祖先就是右子树找到的结点
       TreeNode right = lowestCommonAncestor(root.right, p, q);

        //假如这是第一次递归的内容，那么进行到这一步，我们可以得到以下信息
        // 1. 首先root节点不为null，同时root即不等于p也不等于q，否则直接返回，程序就会执行到这个地方
        // 2. TreeNode left = lowestCommonAncestor(root.left, p, q);left可以看作是根节点的左子树最终的查找结果，可以为null或者是最近的公共祖先节点
        // 3. TreeNode right = lowestCommonAncestor(root.right, p, q);right可以看作是根节点的右子树最终的查找结果，可以为null或者是最近的公共祖先节点
        // 4. 接下来需要进行判断共三种情况：
        //(1) left为null，那么right就是结果
        //(2) right为null，那么left就是结果
        //(3) 如果两者都不是null，说明p和q分别在root的左右子树中，那么root就是最近的公共祖先节点
       if (left == null)
           return right;
       if (right == null)
           return left;
       return root;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(int val) {
        this.val = val;
    }
}